package org.leetcode.easy.leetcode1047;

import java.util.*;

public class Solution
{

    public String removeDuplicates2(String s)
    {

//        ArrayDeque<Character> deque = new ArrayDeque<>();
        LinkedList<Character> deque = new LinkedList<>();

        char ch;

        for (int i = 0; i < s.length(); i++)
        {
            ch=s.charAt(i);

            //if (deque.isEmpty() || deque.peek() != ch) {
            //                deque.push(ch);
            //            } else {
            //                deque.pop();
            //            }

            if ( deque.peek()!=null && ch==deque.peek() )
            {
                deque.pop();
            }else {
                deque.push(ch);
            }
        }

        String str ="";

        while (!deque.isEmpty())
        {
            str=deque.pop()+str;
        }

        return str;

    }




    /**
     * 超时
     * @param s
     * @return
     */
    public String removeDuplicates(String s)
    {
//        Deque<Character> stack=new LinkedList<Character>();
//
//        for (int i = 0; i < s.length(); i++) {
//            stack.add(s.charAt(i));
//        }
//        stack.get
        ArrayList<Character> arrayList = new ArrayList<>();

        for (int i = 0; i < s.length(); i++) {
           arrayList.add(s.charAt(i));
        }

        int slow =0;
        int fast =1;

        while (fast<=arrayList.size()-1)
        {
            if (arrayList.get(slow)==arrayList.get(fast))
            {
                arrayList.remove(slow);
                arrayList.remove(slow);
                slow=0;
                fast=1;
            }else {
                slow++;
                fast++;
            }
        }

        String res ="";

        for (Character c :arrayList)
        {
            res=res+c;
        }

        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String result = solution.removeDuplicates2("azxxzy");
        System.out.println(result);
    }
}
